#!/usr/bin/python3
""" 优先队列的实现  """
from .heapsort import *


class MaxPriorityQueue:
    """
    最大优先级队列
    常用于事件规划
    """
    def __init__(self):
        self.array_key = []
        self.array_value = []

    def insert(self, key, value):
        """ 插入一个对象  """
        pass

    def maximum(self):
        """ 返回当前队列的拥有最大key值的value  """
        return self.array_key[python_index(1)]
        
    def extract_max(self):
        """ 删除并返回拥有最大值key的value  """
        heap_size = len(self.array_key)
        if heap_size < 1:
            raise Exception("heap underflow")
        max = self.array_key[python_index(1)]
        self.array_key[python_index(1)] = self.array_key[python_index(heap_size)]
        heap_size = heap_size - 1
        max_heapify(self.array_key, 1, heap_size=heap_size)
        return max

    def _increase_key(self, index, key):
        real_index = python_index(index)
        if key < self.array_key[real_index]:
            raise Exception("new key is smaller than current key")
        self.array_key[real_index] = key
        while index > 1 and self.array_key[python_index(p_parent(index))] < self.array_key[index]:
            pass


class MinPriorityQueue():
    """ 
    最小优先级队列  
    min-priority队列一般被用来用于事件驱动模拟
    """
    
    def __init__(self):
        pass

    def insert(self, key, value):
        pass

    def minimum(self):
        pass

    def extract_min(self):
        pass

    def decrease_key(self, key, value):
        pass
